\documentclass[a4paper,11pt]{article}

% \usepackage{fontspec}           % 用XeTeX排版中文需要用到的一个宏包
\usepackage{xeCJK}
% \usepackage{indentfirst}        % 自动首行缩进
\usepackage{graphicx}           % 插入图片需要的宏包
\usepackage{amssymb}            % AMS的数学宏包, 有时需要用到其中的一些数学符号
\usepackage{color}              % 可以定义各种颜色
\usepackage{framed}             % 显示代码环境的制作需要用到
\usepackage{float}              % 强大的浮动环境控制宏包
\usepackage[pagestyles]{titlesec}         % 定制页眉页脚
\usepackage[pdfauthor={Crazy Maze Group},%
            pdftitle={迷宫问题小组报告},%
            colorlinks=true,%
            urlcolor=blue]{hyperref} % 为超链接增加颜色, 还有一些其它的好用功能
\usepackage[top=1in,bottom=1in,left=1.25in,right=1.25in]{geometry} % 设置页边距

\title{\textbf{{成都信息工程学院软件工程学院}\\
               {2008$\sim$2009学年第1学期}\\
               {数据结构课程设计报告}\\[0.5cm]
               {题目：迷宫求解}\\[2cm]}}
\date{日期：2009年1月5日}
\author{{学生：丁睿\quad{}学号：2007081102\quad{}班级：软工（.NET）1班}\\
        {学生：高昌健\quad{}学号：2007081107\quad{}班级：软工（.NET）1班}\\
        {学生：杨进\quad{}学号：2007081116\quad{}班级：软工（.NET）1班}\\
        {学生：李小兰\quad{}学号：2007081133\quad{}班级：软工（.NET）2班}\\[0.5cm]
        {指导老师：黄健老师}}

% 自定义的几种颜色
\definecolor{shadecolor}{gray}{0.85}
\definecolor{darkblue}{RGB}{52,101,164}
\definecolor{darkgreen}{RGB}{78,154,6}

% 设置背景颜色
% \definecolor{bisque}{rgb}{.996,.891,.755}
% \pagecolor{bisque}

% 字体设置和针对中文的断行标准
\setmainfont[BoldFont=Adobe Heiti Std]{Adobe Song Std}
\setCJKmainfont[BoldFont=Adobe Heiti Std]{Adobe Song Std}
% \setsansfont{DejaVu Sans YuanTi Mono}
% \XeTeXlinebreaklocale ''zh''
% \XeTeXlinebreakskip=0pt plus 1pt minus 0.1pt

% 设置原文照排环境的字体
% \makeatletter
% \def\verbatim@font{\sffamily\small}
% \makeatother

% 设置chapter, section与subsection的格式
\titleformat{\chapter}{\centering\huge}{第\thechapter{}章}{1em}{\textbf}
\titleformat{\section}{\LARGE}{\thesection}{1em}{\textbf}
\titleformat{\subsection}{\Large}{\thesubsection}{1em}{\textbf}

% 设置页眉页脚
% \newpagestyle{main}{%
%   \sethead[$\cdot$~\thepage~$\cdot$][][\thesection\quad%
%   \sectiontitle]{\thesection\quad\sectiontitle}{}{%
%   $\cdot$~\thepage~$\cdot$}
%   \setfoot{}{}{}\headrule}
% \pagestyle{main}
% \renewpagestyle{plain}{\sethead{}{}{}\setfoot{}{}{}}

% 去掉表头中的冒号
\makeatletter
\long\def\@makecaption#1#2{%
\vskip\abovecaptionskip
\sbox\@tempboxa{#1~~#2}%
\ifdim \wd\@tempboxa >\hsize
   #1~~#2\par
\else
   \global \@minipagefalse
   \hb@xt@\hsize{\hfil\box\@tempboxa\hfil}%
\fi
\vskip\belowcaptionskip}
\makeatother

% 将默认的英文重定义为中文
\renewcommand{\contentsname}{目录}
\renewcommand{\listfigurename}{插图目录}
\renewcommand{\listtablename}{表格目录}
\renewcommand{\refname}{参考文献}
% \renewcommand{\abstractname}{摘要}
\renewcommand{\indexname}{索引}
\renewcommand{\tablename}{表}
\renewcommand{\figurename}{图}

\setlength{\parindent}{2.22em}  % 设置首行缩进的距离
\linespread{1.3}                % 设置行距

% XeTeX logo
\def\XeTeX{\leavevmode
  \setbox0=\hbox{X\lower.5ex\hbox{\kern-.15em\reflectbox{E}}\kern-.1667em 
    \TeX}%
  \dp0=0pt\ht0=0pt\box0}

\begin{document}
\maketitle

\begin{center}
  {\Large\textbf{迷宫求解问题}}
\end{center}

\section{设计目的}
仅认识到栈是一种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解栈的特征，以便在实际问题背景下灵活运用它，同时还将巩固这种结构的构造方法。

\section{问题描述}
取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置以块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图所示，求出一条从入口到出口的通路，或得出没有通路的结论。
\begin{figure}[H]
  \centering
  \includegraphics[scale=.5]{maze_example.png}
\end{figure}

\section{设计要求}
要求设计程序输出如下：

(1) 建立一个大小为m$\times$n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来；

(2) 找出一条通路的二元组(i,j)数据序列，(i,j)表示通路上某一点的坐标。

(3) 用一种标志在迷宫中标出标出该条通路；

(4) 在屏幕上输出迷宫和通路；

(5) 上述功能可用菜单选择。

\section{小组中各个成员担任的角色}
丁睿：提供初期迷宫测试的所有代码，负责最终代码的动态打印模块，帮助改进了回溯算法，并绘制地图文件。

高昌健：负责最终代码的随机加载地图文件模块，菜单模块，综合其他小组成员的代码，以及后期调试。

杨进：负责迷宫求解的核心算法——回溯算法。

李小兰：负责迷宫游戏的所有代码，并绘制地图文件。

期间，很多想法都是小组成员共同讨论决定的。

\section{需求分析}
我们小组做的迷宫程序主要有两个功能：迷宫求解和迷宫游戏。

迷宫求解是采用随机加载地图文件来初始化迷宫，然后使用回溯算法来寻求相对最优路径，最后动态打印。

迷宫游戏则分为3个游戏等级：迷宫新手、进阶冒险和终极挑战。玩家可以使用方向键来控制地图上的标志移动，并躲避一定的障碍，最后走出迷宫。玩家可以通过检查自己移动的步数来判定自己的成绩。

\section{模块说明}
\begin{center}
  {\Large\textcolor{darkblue}{\textbf{迷宫求解模块说明}}}
\end{center}
\subsection{建造迷宫（\texttt{create\_maze.c \& load\_maze.c}）}
随机读取map子目录中的地图文件，并加载其中的地图数据构造迷宫。流程图如下：
\begin{figure}[H]
  \centering
  \includegraphics[scale=.4]{loadmaze_flowchart.png}
\end{figure}
\subsection{寻找相对最优路径（\texttt{backtrace.c}）}
构造好迷宫以后，就利用回溯算法寻找相对最优路径，所谓相对最优路径即在步数尽可能少的情况下走出迷宫。使用链表来存储路径上的每一个点。流程图如下：
\begin{figure}[H]
  \centering
  \includegraphics[scale=.6]{backtrace_flowchart.png}
\end{figure}
\subsection{动态打印（\texttt{dynamic\_print.c}）}
通过回溯算法找到的相对最优路径，将路径以动态打印的方式演示出来。流程图如下：
\begin{figure}[H]
  \centering
  \includegraphics[scale=.6]{dynamicprint_flowchart.png}
\end{figure}
\begin{center}
  {\Large\textcolor{darkblue}{\textbf{迷宫游戏模块说明}}}
\end{center}

通过读取键盘按键来控制小人的移动，级别1为迷宫新手，可任意穿越墙壁，级别2为进阶冒险，不可任意穿越墙壁，级别3为终极挑战，可任意穿越墙壁，但得小心不能踩到地图上的炸弹。流程图如下：
\begin{figure}[H]
  \centering
  \includegraphics[scale=.6]{mazegame_flowchart.png}
\end{figure}

\section{调试记录}
\subsection{运行程序}
运行画面如下，这是程序的主菜单：
\begin{figure}[H]
  \centering
  \includegraphics[scale=.8]{main_menu.png}
\end{figure}
\subsection{迷宫求解}
选择第一个选项以后，进入迷宫求解，准备画面如下：
\begin{figure}[H]
  \centering
  \includegraphics[scale=.6]{prepare.png}
\end{figure}
然后按任意键开始自动演示，演示结果如下：
\begin{figure}[H]
  \centering
  \includegraphics[scale=.6]{after_print.png}
\end{figure}
\subsection{迷宫游戏}
选择主菜单的第二个选项以后就进入了迷宫游戏的子菜单，显示如下：
\begin{figure}[H]
  \centering
  \includegraphics[scale=.8]{game_menu.png}
\end{figure}
游戏初始画面如下：
\begin{figure}[H]
  \centering
  \includegraphics[scale=.6]{game_start.png}
\end{figure}
当走到出口以后，游戏就结束了，显示如下：
\begin{figure}[H]
  \centering
  \includegraphics[scale=.6]{game_end.png}
\end{figure}
如果你选择的是终极挑战，那么当你不小心碰到了炸弹的话，就会像下面这样：
\begin{figure}[H]
  \centering
  \includegraphics[scale=.6]{game_over.png}
\end{figure}

\section{小结}
刚开始拿到这个题目时，我们选择每个人先试着参照书上的算法来写一个迷宫出来，最终有两个人写出来了，并且可以随机生成迷宫和动态演示。但我们很快就发现了这种玩具程序的弊端：迷宫不够复杂，并且路径不是最优路径，存在很多弯路。于是我们就开始着手讨论解决这两个难题。

首先是怎样增加迷宫的复杂程度？随机的概率不好控制，很容易造成死迷宫，于是经过商量，我们决定采用自己绘制迷宫，然后存储到地图文件中，运行的时候再随机加载。这样就解决了迷宫不够复杂的问题，但就需要大量的地图文件来达到随机的效果。由于时间缘故，我们只绘制了小部分的地图，但由于我们采用的地图存储结构比较灵活，就很适合于以后的扩展。

然后就是寻找最优路径。教材上的那个算法太死板，造成得到的路径是唯一的，于是我们寻求到了另一个适合迷宫的算法——回溯算法。简单理解回溯就是将一个点可以走的四个方向看成四种情况向下分解，然后不停的递归，直到到达终点或者再也没有路径可走了。但如果地图太复杂的话，就会存在很多条通路，我们在测试的时候曾经在一个地图上找到了几千万条通路，这样递归下去需要很长的时间。于是我们决定适当地控制递归的次数，这样得到的路径虽然不一定是最优的，但在一定概率的范围内可以保证是相对最优的。

最后还增添了一个很有趣的功能：迷宫游戏，让每个人都可以乐在其中。

这次的课程设计让我们有了很多新的尝试，虽然不像预期的那样精美和复杂，但我们都加深了对于相关知识的掌握。这是我们努力的成果。

\begin{thebibliography}{99}
  \bibitem{DS} 严蔚敏, 吴伟民. 数据结构：C语言版. 清华大学出版社, 2007
  \bibitem{C} Brian W. Kernighan, Dennis M. Ritchie. The C Programming Language, 2nd Edition.
\end{thebibliography}
\end{document}